/* 119. 杨辉三角 II */
/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function (numRows) {
    numRows = numRows + 1
    const result = new Array(numRows).fill(0).map((_, i) => new Array(i + 1).fill(1))
    for (let i = 2; i < result.length; i++) {
        for (let j = 1; j < result[i].length - 1; j++) {
            result[i][j] = result[i - 1][j - 1] + result[i - 1][j]
        }
    }
    return result[numRows - 1]
};

/* 滚动数组空间复杂度优化 */
var getRow = function (numRows) {
    let pre, cur
    for (let i = 0; i <= numRows; i++) {
        cur = new Array(i + 1).fill(0)
        cur[0] = cur[i] = 1
        for (let j = 1; j < i; j++) {
            cur[j] = pre[j - 1] + pre[j]
        }

        pre = cur
    }

    return pre
}

var getRow = function (rowIndx) {
    const row = new Array(rowIndx + 1).fill(0)
    row[0] = 1
    for (let i = 1; i <= rowIndx; i++) {
        for (let j = i; j > 0; j--) {
            row[j] += row[j - 1]
        }
    }
    return row
}

/* 记忆化递归 */
var getRow = function (rowIndex) {
    const memo = new Array(rowIndex + 1).fill(0).map((_, i) => new Array(i + 1).fill(0))
    for (let j = 0; j < rowIndex + 1; j++) {
        memo[rowIndex][j] = cal(rowIndex, j, memo)
    }

    return memo[rowIndex]
}

var cal = function (i, j, memo) {
    if (j === 0 || i === j) return 1 // base
    if (memo[i][j]) return memo[i][j]

    memo[i][j] = cal(i - 1, j - 1, memo) + cal(i - 1, j, memo)
    return memo[i][j]
}
getRow(4)